package com.culture.bootdemo.算法.sort;

import java.util.*;

/**
 * @author: wen
 * @date 2020/9/28
 * 堆排序  升序大顶堆，降序小顶堆
 * 时间复杂度：O(nlog n)
 * eg: 也可以使用 优先队列实现小顶堆
 */
public class DuiSort {

    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 4, 5, 4, 10, 2, 1, 3, 54, 2, 34};
        sort(arr);
        System.out.println("大顶堆，升序:" + Arrays.toString(arr));

        int[] arr2 = {9, 8, 7, 4, 5, 4, 10, 2, 1, 3, 54, 2, 34};
        heapSort(arr2);
        System.out.println("小顶堆，降序:" + Arrays.toString(arr2));

        int[] arr1 = {9, 8, 7, 4, 5, 4, 10, 2, 1, 3, 54, 2, 34};
        int k = 5;
        List<Integer> integers = solutionByHeap(arr1, k);
        System.out.println("top k 问题，k = " + k + ",用优先队列解决:" + integers);
    }



    //构建大顶堆： 升序算法
    public static void sort(int[] arr) {
        //1.构建大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr, i, arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for (int j = arr.length - 1; j > 0; j--) {
            swap(arr, 0, j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr, 0, j);//重新对堆进行调整
        }

    }


    /**
     * 使用小顶堆 --->从大到小排序
     *
     * @param arr
     */
    public static void heapSort(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            //构建小顶堆 :从 arr.length/2-1 即倒数第一个非叶子节点开始，逐一下滤，
            perDownMin(arr, i, arr.length);
        }
        for (int i = arr.length - 1; i > 0; i--) {
            //将根节点，即最小的节点与最后一个节点交换，让最小值逐一放在最后
            swap(arr, i, 0);
            //从根节点开始重新生成小顶堆
            perDownMin(arr, 0, i);
        }
    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     *
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];//先取出当前元素i
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始，也就是2i+1处开始
            if (k + 1 < length && arr[k] < arr[k + 1]) {//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if (arr[k] > temp) {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }


    /**
     * 小顶堆下滤
     *
     * @param arr
     * @param i
     * @param length
     */
    private static void perDownMin(int[] arr, int i, int length) {
        int child;
        int temp;

        for (temp = arr[i]; leftChild(i) < length; i = child) {
            child = leftChild(i);
            if (leftChild(i) != length - 1 && arr[child + 1] < arr[child]) {
                child++;
            }
            if (temp > arr[child]) {
                arr[i] = arr[child];
            } else {
                break;
            }
        }
        arr[i] = temp;
    }

    private static int leftChild(int i) {
        return 2 * i + 1;
    }

    /**
     * 交换元素
     *
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }



    /**
     * 优先队列实现小顶堆
     *
     * @param input
     * @param k
     * @return
     */
    public static List<Integer> solutionByHeap(int[] input, int k) {
        List<Integer> list = new ArrayList<>();
        if (k > input.length || k == 0) {
            return list;
        }
        Queue<Integer> queue = new PriorityQueue<>();
        for (int num : input) {
            if (queue.size() < k) {
                queue.add(num);
            } else if (queue.peek() < num) {
                queue.poll();
                queue.add(num);
            }
        }
        while (k-- > 0) {
            list.add(queue.poll());
        }
        return list;
    }


}
